A lot of applications, like simulation, gaming, statistics, cryptography and generally security applications, etc., require use of random number generators.
Generally, existing random number generators can be subdivided into two main categories: hardware-based generators and software-based generators.
Hardware-based generators, commonly referred to as True Random Number Generators (TRNG), exploit randomly occurring physical phenomena like electrical noise, oscillator jitter, flip-flop metastability and so on. When using a true random number generator, measures are to be taken to avoid that the generated sequence is affected by biasing (the tendency to preferably generate either of the two digital values), short term auto-correlation and other deviations from randomness, as disclosed for instance the paper “Hardware Random Number Generators” presented by R. Davies at the 15th Australian Statistics Conference, July 2000, and published on Oct. 14, 2000 on the Internet site http://www.robertnz.net. The main problem with such generators is that, being the physical principle on which they are based actually random, they do not guarantee a specified output bit rate and the bit rate itself is not very high. This makes TRNGs unsuitable for applications like simulations, real-time cryptography e.g. in telecommunications, etc.
Software generators, commonly referred to as Pseudo-Random Number Generators (PRNG), are deterministic generators that use an algebraic algorithm to create a periodic sequence of random numbers with a very long period that depends on the generator architecture. A number of architectures for such generators are disclosed in “Applied Cryptography: Protocols, Algorithms and Source Code in C”, by B. Schneier, 2nd Edition, 1996, J. Wiley & Sons, Inc., see in particular Chapter 16. These generators can operate at a predetermined and relatively high bit rate. Yet, since the sequence is based on an algorithmic process, it is possible to guess the random number n+1 if the random number n is known. This can allow a recovery of the “seed” used for the generation. In some applications, e.g. simulation, this is not important and is not a problem for the correct work of the application. In other cases, e.g. cryptography and security applications, the possibility of recovering the seed, even with a considerable effort, is of course a weakness in the security chain.
A commonly adopted solution to overcome the above problems is to combine a true random generator and a pseudo-random generator and to use the output of the true random generator to alter the pseudo-random sequence, which forms the output sequence. For instance, the true random numbers are uses as seed for the pseudo-random generator. The use of a pseudo-random generator solves the problem of the low bit rate of the hardware generator. Continuously modifying the output of the pseudo-random generator by using the true random sequence tries to overcome the problem of the deterministic nature of the pseudo-random number generator.
Several implementations of that solution are known in the art.
The above mentioned paper of R. Davies suggests to merge the bit streams from the PRNG and the TRNG by means of a simple EX-OR operation.
Somewhat more sophisticated techniques exist in the patent literature.
U.S. Pat. No. 6,408,317 modifies a PRNG in the form of a Linear Feedback Shift Register (LFSR) by using a condenser function to calculate a bit stream to be EXORed with the output of the LFSR itself. Moreover the feedback function of the LFSR is modified continuously by the random bits coming at constant bit rate from a TRNG. Thus, the output bit stream should have the same bit rate as the TRNG. The device disclosed in that document cannot obtain high bit rates and, moreover, it exploits only one randomness factor, i.e. the random value of the TRNG sequence.
US-A 2003/0059046 includes a deterministic generator composed by three LFSRs, the interaction among which is modified through a scrambling function driven by a TRNG emitting a constant bit-rate sequence. Also in that case only one randomness factor is exploited.
US-A 2002/0156819 also modifies a LFSR acting as PRNG through an EX-OR operator at the input of the LFSR itself. In this case the modifying signal is generated by means of the interaction of three free-running oscillators having different oscillation frequencies, different also from that of the system clock driving the LFSR. Also in this case only the random value of the EX-OR output can be exploited, since the time dependence in the modifying signal is very weak, is strongly correlated and is mostly deterministic. Indeed, the modifying signal is fed to the LFSR after having been latched by using the system clock so that a modifying signal at constant bit rate is obtained.
Thus, all such prior proposals for modifying the behaviour of the pseudo-random generator are based on techniques that use a single randomness factor, so that they are rather simple and do not guarantee a good and deep interaction with the PRNG. Thus, a non-negligible possibility of attack still exists.
It is a main object of the invention to provide a random number generator and a method of random number generation, which are based on the alteration of a pseudo-random sequence by means of a true random sequence, and in which a more sophisticated technique for modifying the behaviour of the pseudo-random generator is used, by exploiting both the random value and the random arrival of the bits in the true random sequence.